package com.dateConstruction._06_tree;

public class Tree<T> {
    
    // 根节点，树的父母孩子兄弟链表结点类型
    public TreeNode<T> root;
    
    // 构造空树
    public Tree() {
        this.root = null;
    }
    
    // 判断是否为空二叉树
    public boolean isEmpty() {
        return this.root == null;
    }
    
    // 拷贝构造方法，算法同三叉链表存储的二叉树
    public Tree(Tree<T> tree) {
        this.root = copy(tree.root, null);
    }
    
    // 深拷贝，复制以p根为子树，parent是复制子树的父母结点，返回新建子树的根节点
    public TreeNode<T> copy(TreeNode<T> p, TreeNode<T> parent) {
        if (p == null) {
            return null;
        }
        TreeNode<T> q = new TreeNode<T>(p.data, p.level, parent, null, null);
        q.child = copy(p.child, q);
        q.sibling = copy(p.sibling, parent);
        return q;
    }
    
    // 插入元素x作为根节点，原根结点作为其孩子结点，返回插入结点
    public TreeNode<T> insertRoot(T x) {
        this.root = new TreeNode<T>(x, 1, null, this.root,null);
        if (this.root.child != null) {
            this.root.child.parent = this.root;
            setLevel(this.root.child, this.root.level+1);
        }
        return this.root;
    }
    
    // 设置以p结点为根子树的所有结点层次
    protected void setLevel(TreeNode<T> p, int level) {
        if (p != null) {
            p.level = level;
            setLevel(p.child, level+1);
            setLevel(p.sibling, level);
        }
    }

    // 返回树的横向凹入表示字符串，以先根次序遍历树
    public String toString() {
        return "树的横向凹入表示：\n" + toString(root, "");
    }
    
    // 先根次序遍历以p为根的子树，tab指定缩进量，返回子树的横向凹入表示字符串，递归算法
    public String toString(TreeNode<T> p, String tab) {
        if (p == null) {
            return "";
        }
        return tab + p.data.toString() + "\n" + toString(p.child, tab + "\t") + toString(p.sibling, tab);
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        // 返回树的横向凹入表示字符串，以先根次序遍历树
        Tree<String> tree0 = new Tree<String>();
        tree0.root = new TreeNode<String>("A");
        tree0.root.child = new TreeNode<String>("B");
        tree0.root.child.sibling = new TreeNode<String>("C");
        tree0.root.child.sibling.sibling = new TreeNode<String>("D");
        tree0.root.child.child = new TreeNode<String>("E");
        tree0.root.child.child.sibling = new TreeNode<String>("F");
        tree0.root.child.sibling.sibling.child = new TreeNode<String>("D");
        tree0.root.sibling = new TreeNode<String>("H");
        tree0.root.sibling.child = new TreeNode<String>("I");
        tree0.root.sibling.child.child = new TreeNode<String>("J");
        System.out.println(tree0);
        
        
    }

}
